/*
COPYRIGHT NOTICE: This software is provided by Canada Post Corporation (CPC). 
It can be used for postal ID-tag applications only. The software may be 
freely distributed and /or modified.  A condition of such distribution is that 
this copyright notice is always included in the comments heading the software. 
This software is licensed as is without any other warranty of any kind. 
CPC expressly disclaims all warranties or conditions including, but not 
limited to, implied warranties or conditions of merchantability and fitness 
for particular purpose and those arising by statute or otherwise in law or from 
course of dealing or usage of trade. In no event shall CPC be liable for any 
direct, indirect, special, incidental, consequential or other damages arising 
out of this software even if CPC has been advised of the possibility of such 
damages in advance.
*/ /* $Id$ */
/* $Log$ */
/* REED-SOLOMON DECODER / PREPROCESSOR FOR 0-1 CODES OVER GF(23).
Description: This program receives a 78-bit string of {0,1} representing the 
encoded data with parity symbols and start/stop bits as the input and it generates 
a 56 bit string of {0,1} representing the encoded data as the output.

The input consists of a start bit, 14 four bit data symbols in the range 0-15 
followed by 4 five bit parity symbols which are encoded using a lookup table which 
restricts run lengths of consecutive zeros, and a stop bit. Since the Reed-Solomon 
code is defined over the field of 23 elements, parity symbols in the range 23-31 
indicate that the symbol is in error. Erased bits are indicated in the received 
codeword by the bit value 4.

Error and erasure decoding of the Reed-Solomon codeword is achieved via the 
Euclidean algorithm (see Clark and Cain for the actual algorithm).

The output is the 56 (14x4) data bits.

This version of the program implements a preprocessor which attempts to locate the 
encoded sequence in a set of bars which is not necessarily of appropriate length. 
It does this according to the following rules:

1)	If the number of bars is greater than the nominal length (78) the 
preprocessor will select subsets of length 78 which start with a 1 and it will call 
the decoder with the 76 bit relevant portion. If the decode is successful, it will 
pass the decoded data through a postprocessing filter to check that the data is 
consistent with other constraints which have been imposed on the input data. If that 
process is successful, it will compute the number of bits which are the same in the 
data portion of the original sequence and the corrected sequence and store this for 
later use. If the decoding is again successful the number of matching bits is once 
again computed and compared to the stored value. If the new value is greater than 
the stored value, it replaces the stored value and the preprocessor continues. If 
they are equal, both successful decodes represented by these values are considered 
to have failed and processing continues. After all possible attempts have been made, 
the data representing the best successful decode, if any, is returned to the calling 
program.

2)	If the number of bars is less than the nominal length (78) the preprocessor 
will pad the beginning of the sequence with enough 4's to increase the length of the 
sequence to the nominal length. It will also pad the end of the sequence with the 
same number of 4's so that the final length is longer than the nominal length by the 
difference between the nominal length and the initial length. If the number of bars 
is greater than or equal to 62 and less then 65 then only one decoding attempt is 
made with the relevant portion of the rightmost 78 bars. Otherwise two decoding 
attempts are made, the first with the relevant portion of the leftmost 78 bars, the 
other with the relevant portion of the rightmost 78 bars. If both attempts are 
successful the matching bit strategy described in (1) above is used to choose the 
better of the two, or to reject both decodes if the number of matching bits is equal.

3)	If the number of bars is equal to the nominal length and the first or last 
bar is not 1 then the sequence is padded with a 4 at the start and end of the 
sequence and subjected to step 1 above. 

4)	If the number of bars is equal to the nominal length and the sequence starts 
and ends with a 1 then only one attempt is made to decode the data.

The program also implements a data validation filter that checks the data to ensure 
that it falls within the allowable range. The limits currently imposed on the data are:
	bottom two bits of F0 with F1 (day of the month) must be 01-31.
	F2 (month) must be 1-12.
	F3 (GMT hour) must be 0-11.
	low order 3 bits of F4 (tens of minutes) must be 0-6.
	F5 to F12 must be 0-12.
	high order 3 bits of F13 must be 0-6. 

where Fn indicates field n of the decoded data and all constraints listed above refer 
to the original (unencoded) data and not to the data as it is actually received by the 
decoder, as the latter is subjected to various lookup tables to restrict runs of 
consecutive zeros.

The month check described in the preceding paragraph (i.e. 1-12) is enhanced by a check 
that the month is no more than 3 months back from or no more than one month forward 
from the current month. This check is controlled by a command line switch (-d) which 
disables the check. The data validation filter is used to both preprocess and postprocess 
the data depending on the value of one of its input arguments. If the argument indicates 
that the function is being used as a preprocessing filter, all of the data symbols are 
checked and incorrect symbols are flagged by adding 64 to the value of the symbol. In the 
postprocessing mode of operation, the data is not modified and the function returns a 0 
error indicator as soon as it locates an invalid symbol.
*/
static char rcsid[] = "$Id$";
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
 //#include <sys/types.h>
#include <time.h>

/* global constants */

#include "common.h"
#include "decode23.h"
/* Define data type for small integers. */
#define INT8 unsigned char
#define SINT8 char
#define BOOLEAN char
const INT8 n = 18;     /* total number of symbols */
const INT8 k = 14;     /* number of 4 bit data symbols */
const INT8 n_k = 4;    /* n - k */
const INT8 n_1 = 17;   /* n - 1 */
const INT8 t = 2;      /* n - k divided by 2 */
const INT8 t2_1 = 3;   /* t2 - 1 */
const INT8 prime = 23;
const INT8 prim_element = 5;
/* Global definitions and prototypes for decode23 */
#define MINLEN 62
#define MIDLEN 65
#define MAXLEN 88
#define LENGTH 78 
#define PADLEN 94
const INT8 alog[23] = {
    1,  5,  2, 10,  4, 20,  8, 17, 16, 11,  9, 22,
   18, 21, 13, 19,  3, 15,  6,  7, 12, 14,  1
};
const INT8 inv[23] = {
    0,  1, 12,  8,  6, 14,  4, 10,  3, 18,  7, 21,
    2, 16,  5, 20, 13, 19,  9, 17, 15, 11, 22
};
const INT8 lookup[32] = {
   64, 64, 64, 64, 64, 64, 64, 64, 22, 21, 20, 19, 18, 17, 16, 15,
   64, 13, 12, 11, 10,  9,  8,  7, 14,  6,  5,  4,  3,  2,  1,  0
};
/* function prototypes */
int convert (int month, int binary[], int codeword[], int v[]);
int decode (int codeword[], int v[], int degv);
int preprocess (int n, int b[], int c[], int month, int *tries, int maxtries);
int validate (int c[], int prescan, int month);
void make_out_data (int codeword[], char output[]);
int checksum (int b[], int c[]);
/* main program */
void main (int argc, char *argv[])
{  
  int i,j;
  FILE *fd;
  int nline;
  int binary[100];
  int codeword[18];
  BOOLEAN output_stats = 0;
  struct tm *current_date_and_time;
  int nbar, tries, maxtries = 99;
  int checkdate = 1;
  char output[56];
  char buf[100];
  char *cp;
  time_t q;

#ifdef TURBOC
  clock_t start, end;
#endif

  if (argc < 2) {
     fprintf (stderr, "\n%s\n",rcsid);
     fprintf (stderr, "\nDecoder for 0-1 codes over GF(23).\n\n");
fprintf (stderr, "Usage: decode23 [-s] [-b] [-d] [-m maxtry] infile\n");
fprintf (stderr, "  s requests information about performance (stats).\n");
     fprintf (stderr, "  b requests that the bars passed to the decoder be printed.\n");
fprintf (stderr, "  d disables check for valid month (3 back, 1 forward).\n");
     fprintf (stderr, "  m sets the number of times that the decoder can be called (default %d).\n",maxtries);
#if defined(TURBOC) 
     fprintf (stderr, "\nCompilation options exercised:\n");
     fprintf (stderr, "  TURBOC");
#endif
fprintf (stderr, "\n");
     exit(1);
  }
  cp = NULL;
  for (i = 1; i < argc; i++) 
    if (strcmp(argv[i],"-s") == 0) 
      ++output_stats;
else if (strcmp(argv[i],"-d") == 0) 
      checkdate = 0;
    else if (strcmp(argv[i],"-m") == 0) 
      maxtries = atoi(argv[++i]);
    else
      cp = argv[i];
  if (cp == NULL) {
     fprintf(stderr, "ERROR - No filename specified.\n");
     exit(1);
  }
  if (maxtries <= 0) maxtries = 1;
  if ((fd = fopen (cp, "r")) == NULL) {
     fprintf (stderr, "Unable to open input file %s.\n", cp);
     exit(1);
  }
  nline = 0;

#ifdef TURBOC
  start = clock ();
#endif

  if (checkdate && time(&q)) {
     current_date_and_time = gmtime(&q);
     if (current_date_and_time != NULL) 
       checkdate = current_date_and_time->tm_mon + 1;
  } else {
     checkdate = 0;
  }
   
  while (fgets (buf, sizeof (buf), fd)) {
     ++nline;
     nbar = strlen (buf);
     while ((nbar > 0) && (buf[nbar-1] == '\n' || buf[nbar-1] == '\r' || buf[nbar-1] == ' '))
       nbar = nbar - 1;
     while ((nbar > 0) && (buf[nbar-1] == '0' || buf[nbar-1] == '4'))
       nbar = nbar - 1;
     j = 0;
     while ((nbar > 0) && (buf[j] == '0' || buf[j] == '4')) {
	nbar = nbar - 1;
	j++;
     }
     nbar = nbar < MAXLEN ? nbar : MAXLEN;
     if (nbar == 0) continue; /* skip blank lines - no error message */
     if (nbar < MINLEN) {
        fprintf (stderr, "ERROR - Invalid input at line %d.\n", nline);
        fprintf (stderr, "        Too few bars to decode.\n");
        continue;
     }
     
     for (i = 0; i < nbar; i++) {
        if (buf[i+j] != '0' && buf[i+j] != '1' && buf[i+j] != '4') {
           fprintf (stderr, "ERROR - Invalid input at line %d.\n", nline);
           fprintf (stderr, "        Invalid character at position %d.\n", i+j);
           exit (1);
        } else {
           binary[i] = buf[i+j] - '0';
        }
     }
     tries = 0;
     if (preprocess(nbar, binary, codeword, checkdate, &tries, maxtries) == 1) {
        make_out_data(codeword, output);
        printf("%s\n",output);
     } else {
        printf("Failed to decode data.\n");
     }
     if (output_stats)
       if (tries > 1) 
         printf("Decoder called %d times. Maximum tries was %d.\n", tries, maxtries);
       else
         printf("Decoder called once. Maximum tries was %d.\n", maxtries);

  }

#ifdef TURBOC
  if (output_stats) {
     end = clock ();
     printf("Total time was %f seconds.\n",(end - start) / CLK_TCK);
  }
#endif
}
  exit(0);
}
/* extract the data bars from the decoded symbols */
void make_out_data (int codeword[], char output[])
{
   int i, j, p;
   p = 0;
   for (i = 0; i < k; i++) 
     for (j = 3; j > -1; j--) 
       if ((codeword[i] >> j) & 1)
         output[p++] = '1';
       else
         output[p++] = '0';
   output[p] = '\0';
}
/* count matching bars between original and corrected sequence */
int checksum (int b[], int c[])
{
   int i, j, p;
   int sum = 0;
   const INT8 lookup[23] = {
      31, 30, 29, 28, 27, 26, 25, 23, 22, 21, 20,
      19, 18, 17, 24, 15, 14, 13, 12, 11, 10,  9,  8
   };
   p = 0;
   for (i = 0; i < k; i++) 
     for (j = 3; j > -1; j--) 
       sum += ((c[i] >> j) & 1) == b[p++];
   for (i = k; i < n; i++) 
     for (j = 4; j > -1; j--) 
       sum += ((lookup[c[i]] >> j) & 1) == b[p++];
   return sum;
}
/* pre and post processing filter */
/* checks that data is within allowable range */
/* if preprocessing it modifies the symbol value */
int validate (int c[], int prescan, int month)
{
   int *F;
   int i, j, l;
   const int unmap[23] = {
      -1, 13, 12, 11, 10, 9, 8, 7, 14, 6, 5, 4, 3, 2, 1, 0,
      -1, -1, -1, -1, -1, -1, -1
   };
  
 F = &c[0];  
/* check that the first two bits of F0 (version) are both zero */
/* also check F0 + F1 represents a valid day of the month (01-31) */
   i = unmap[F[0]];
   j = unmap[F[1]];
   if (!prescan) 
   
   	if (!(F[0] & 0x8)){
		return 0;
	}  	
   
     switch (F[0] & 0x3) { /* first digit of day of the month */
      case 3:
	if (j < 1 || j > 9) {  /* check second digit */
	   return 0;
	}
	break;
      case 2:
      case 1:
	if (j < 0 || j > 9) {  /* check second digit */
	   return 0;
	}
	break;
      case 0:
	if (j < 0 || j > 1) {
	   return 0;
	}
	break;
    }
      
/* check for F2 (month) in the range 1-12 */
   if (unmap[F[2]] < 1 || unmap[F[2]] > 12) {
if (prescan) 
	F[2] += 64;
      else
	return 0;
   }
/* check for valid month (3 back, 1 forward) if requested */
   if (month) {
      i = unmap[F[2]];
      j = month + 1;
      j = j > 12 ? 1 : j;
      l = j - i;
      if (l < 0)
	l = 12 + j - i;
      if (l > 4) {
	 if (prescan) 
	   F[2] += 64;
	 else
	   return 0;
      }
   }
/* check for F3 (GMT hour) in the range 0-11 */
   if (unmap[F[3]] < 0 || unmap[F[3]] > 11) {
if (prescan)
	F[3] += 64;
      else
	return 0;
   }
/* check that time of hour part of F4 in the range 0-5 */
   i = unmap[F[4]];
   j = 7 - (F[4] & 7);
   if (i < 0 || j > 5) {
if (prescan) 
	F[4] += 64;
      else
	return 0;
   }
/* check that F5 - F12 are in the range 0-12 */
   for (i = 5; i < 13; i++) {
      if (unmap[F[i]] < 0 || unmap[F[i]] > 12) {
	 if (prescan)
	   F[i] += 64;
	 else
	   return 0;
      }
   }
/* check that the high order 3 bits of F13 are in the range 0-6 */
   i = unmap[F[13]];
   j = (F[13] >> 1) & 7;
   if (i < 0 || j == 0) {
if (prescan) 
	F[13] += 64;
      else
	return 0;
   }

   return 1;
}
/* search for a proper sequence to decode */
int preprocess (int n, int b[], int c[], int month, int *tries, int maxtries)
{
   int *p;
   int i,j,q,l,m;
   int d[PADLEN];
   int degv, v[5];
   int saved[18];
   int tmp, sum;
   int max;
  
 q = n;
   if (n == LENGTH) {
     if (b[0] != 1 || b[LENGTH-1] != 1) {
        d[0] = 4;
        for (i = 0; i < n; i++) 
          d[i + 1] = b[i];
        d[n + 1] = 4;
        n += 2;
        p = &d[0];
     } else {
        p = &b[0];
     }
  } else if (n < LENGTH) {
     j = LENGTH - n;
     for (i = 0; i < j; i++) 
       d[i] = 4;
     d[0] = 1; /* kludge for check in loop below */
     for (i = 0; i < n; i++) 
       d[i + j] = b[i];
     for (i = 0; i < j; i++) 
       d[i + LENGTH] = 4;
      n += 2 * j;
      p = &d[0];
   } else {
      p = &b[0];
   }

   if (n > MAXLEN) return 0;
   j = 0;
   m = 1;
   l = n - LENGTH + 1;
   if (q < MIDLEN) 
     j = l - 1;
   else if (q < LENGTH)
     m = l - 1;
   sum = 0;
   max = 0;
   for (i = j; i < l; i += m) {
      if (p[i] != 1) continue;
      ++*tries;
      if ((degv = convert(month, &p[i+1], c, v)) < n_k)
	if (decode(c, v, degv))
	  if (validate(c,0,month)) {
	     tmp = checksum(&p[i+1], c);
	     if (tmp > max) {
		sum = tmp;
		max = tmp;
		for (q = 0; q < 18; q++)
		  saved[q] = c[q];
	     } else if (tmp == sum)
	       sum = 0;
	  }
      if ((*tries) > maxtries)
	return 0;
   }
   if (sum) {
      for (i = 0; i < 18; i++) 
	c[i] = saved[i];
return 1;
   }

   return 0;
}
int convert (int month, int binary[], int codeword[], int v[])
{
  int i, j, z, w, temp;
  int erase, degv;

/* Convert the received codeword from binary to GF(23) symbols. */
/* First we convert the data symbols. */
  for (i = 0; i < k; i++) {
    temp = 0;
    if (binary[4 * i + 0] == 1)
      temp ^= 1;
    temp <<= 1;
    if (binary[4 * i + 1] == 1)
      temp ^= 1;
    temp <<= 1;
    if (binary[4 * i + 2] == 1)
      temp ^= 1;
    temp <<= 1;
    if (binary[4 * i + 3] == 1)
      temp ^= 1;
    codeword[i] = temp;
  }
/* Next we convert the parity symbols. */
  for (i = 0; i < n_k; i++) {
    temp = 0;
    if (binary[4 * k + 5 * i + 0] == 1)
      temp ^= 1;
    temp <<= 1;
    if (binary[4 * k + 5 * i + 1] == 1)
      temp ^= 1;
    temp <<= 1;
    if (binary[4 * k + 5 * i + 2] == 1)
      temp ^= 1;
    temp <<= 1;
    if (binary[4 * k + 5 * i + 3] == 1)
      temp ^= 1;
    temp <<= 1;
    if (binary[4 * k + 5 * i + 4] == 1)
      temp ^= 1;
    codeword[i + k] = lookup[temp];
  }

/* Apply the data validation filter. */
  validate(codeword,1,month);
/* Determine the erasure polynomial. */
  degv = 0;
  v[0] = 1;
  for (i = 1; i <= n_k; i++)
    v[i] = 0;
  for (i = 0; i < n_k; i++) { /* check parity symbols */
    if (codeword[i + k] < 64) { /* check if already erased */
       erase = 0;
       if (binary[4 * k + 5 * i + 0] == 4) erase |= 1;
       if (binary[4 * k + 5 * i + 1] == 4) erase |= 1;
       if (binary[4 * k + 5 * i + 2] == 4) erase |= 1;
       if (binary[4 * k + 5 * i + 3] == 4) erase |= 1;
       if (binary[4 * k + 5 * i + 4] == 4) erase |= 1;
       if (erase) codeword[i + k] = 0;
    } else {
       erase = 1;
       codeword[i + k] = 0;
    }
    if (erase != 0) {
      if (++degv > n_k) {
return degv;
      }
      w = alog[n_k - i - 1];
      for (j = degv; j > 0; j--)
        v[j] = (v[j] - w * v[j - 1]) % prime;
    }
  }
  for (i = 0; i < k; i++) {
    if (codeword[i] < 64) {
       erase = 0;
       if (binary[4 * i + 0] == 4) erase |= 1;
       if (binary[4 * i + 1] == 4) erase |= 1;
       if (binary[4 * i + 2] == 4) erase |= 1;
       if (binary[4 * i + 3] == 4) erase |= 1;
       if (erase) codeword[i] = 0;
    } else {
       erase = 1;
       codeword[i] = 0;
    }
    if (erase != 0) {
      if (++degv > n_k) {
return degv;
      }
      w = alog[n - i - 1];
      for (j = degv; j > 0; j--)
        v[j] = (v[j] - w * v[j - 1]) % prime;
    }
  }
/* Make sure the erasure polynomial is in the range 0-prime-1. */
  for (z = degv; z >= 0; z--) {
    if (v[z] < 0)
      v[z] += prime;
  }

  return degv;
}
/* DECODE
   This function performs the decoding of the Reed-Solomon codeword.
   Decoding is based on the Euclidean algorithm.
*/
int decode (int codeword[], int v[], int degv)
{
  int i, j, x, z, tau, r, s, w, temp, bound, alpha;
  int syn[5], a[5], b[5], u[5], dv[5], cor[18];
  int errcount, maxerrs, dega, degb, delta, check;

  errcount = 0;
  maxerrs = degv + (n_k-degv)/2;  /* Maximum number of correctable positions.*/
/* Reverse the codeword for our computational purposes. */
  for (i = 0, j = n - 1; i <= j; i++, j--) {
     cor[i] = codeword[j];
     cor[j] = codeword[i];
  }
/* and complement the data symbols. */
  for (i = n_k; i < n; i++)
    cor[i] ^= 15;
/* Recalling that the received vector (codeword) is actually a
   polynomial, evaluate the polynomial at each of the roots of the
   generating polynomial - namely prim_element, prim_element**2, etc.
   Use these calculated values as the coefficients of the syndrome
   polynomial s(x).  
*/
  check = 0;
  for (i = 0; i <= t2_1; i++) {
    x = alog[i + 1];
    s = cor[n_1];
    for (j = n - 2; j >= 0; j--) {
      s = (cor[j] + s * x) % prime;
    }
    syn[i] = s;
check |= s;
  }
/* If the syndrome is 0, no decoding is necessary, as the received
   word is a valid codeword (no errors). 
*/
  if (check == 0) {
return 1;
  }
  syn[n_k] = 0;
/* Euclidean Algorithm (see Clark and Cain) */
  for (i = 0; i <= n_k; i++) {  
    a[i] = u[i] = 0;
    b[i] = syn[i];         /* b[] is initially the syndrome polynomial. */
  }
  a[n_k] = 1;              /* a[] is initially X**m. */
  dega = n_k;
/* Make b[x] = syn(x) erl(x) mod X**m. */

  for (j = 0; j < n_k; j++)
    for (i = 1; i <= j; i++)
      b[j] = (b[j] + v[i] * syn[j - i]) % prime;

/* Calculate the degree of b[]; starting at degb=m-1 effectively
   reduces b(x) mod X**m. */
  for (degb = n_k - 1; b[degb] == 0 && degb > 0; degb--);
  bound = t + (degv >> 1);      /* bound for iterations below */

/* Roll the Euclidean algorithm. */
  while (degb >= bound) {
    delta = dega - degb;
    w = inv[b[degb]];
    for (z = 0; z <= delta; z++) {
      tau = prime - (a[dega - z] * w) % prime;
      for (i = 0; i <= degb; i++) {
        a[delta - z + i] = (a[delta - z + i] + b[i] * tau) % prime;
        u[delta - z + i] = (u[delta - z + i] + v[i] * tau) % prime;
      }
    }
    for (j = 0; j <= dega; j++) {
      temp = a[j];
      a[j] = b[j];
      b[j] = temp;
    }
    for (j = 0; j <= n_k; j++) {
      temp = u[j];
      u[j] = v[j];
      v[j] = temp;
    }
    dega = degb;
    for (degb = degb - 1; b[degb] == 0 && degb > 0; degb--);
    degv += delta;
  }
/* At the end of the Euclidean algorithm, b[] is the error evaluator
   polynomial, and v[] is the error locator polynomial.   */
/* To correct the errors using b[] and v[], the following steps
   must be taken. */
/* first, find the derivative of the error locator */
  for (i = 0; i < degv; i++)
    dv[i] = ((i + 1) * v[i + 1]) % prime;
/* Second, run through the powers prim_element**0, ...,
   prim_element**(-i), ..., looking for the roots of v(x),
   which are the error/erasure locations. */
  for (i = 0; i < n; i++) {
    alpha = alog[i];
    w = inv[alpha];
    s = v[degv];
for (j = degv - 1; j >= 0; j--) {
      s = (s * w + v[j]) % prime;
    }
    if (s == 0) {    /* An error/erasure has been found at cor[i]. */
errcount++;
      r = dv[degv - 1];  /* Calculate correction factor and add to cor[i]. */
      for (j = degv - 2; j >= 0; j--)
        r = (r * w + dv[j]) % prime;
      temp = b[degb];
      for (j = degb - 1; j >= 0; j--)
        temp = (temp * w + b[j]) % prime;
      cor[i] = (cor[i] + temp * inv[r]) % prime;
    }
  }
/* Check to make sure the correct number of errors have been corrected. */
  if (errcount == degv && errcount <= maxerrs) {
     for (i = 0, j = n - 1; i <= j; i++, j--) { /* reverse */
	codeword[i] = cor[j];
	codeword[j] = cor[i];
     }
     for (i = 0; i < k; i++) /* and complement */
       codeword[i] ^= 15;

    return 1;
  }

  return 0;
}
